#include <iostream>
using namespace std;

#define MAX 50

int dp[MAX]; // 该数组的意思为，选出和为j的划分方案有dp[j]种
int n;       // 1~n的连续整数

int divideToEqual()
{
    if (n * (n + 1) % 4 != 0) // 如果一半非整数，则凑不出来
        return 0;

    int sum = n * (n + 1) / 2;
    dp[1] = 1; // 和为1只有{1}
    for (int i = 1; i <= n; i++)
    {
        for (int j = sum / 2; j >= i; j--)
            dp[j] += dp[j - i];
    }

    // 注意，选择方案应该是对称的
    // 比如 {1,4}{2,3}，其实是1种
    return dp[sum / 2] / 2;
}

int main()
{
    memset(dp, 0, sizeof(int) * MAX);
    cout << "请输入连续整数范围n：";
    cin >> n;
    cout << "拆分为相等子集合的方案数：" << divideToEqual() << endl;

    return 0;
}

/*
请输入连续整数范围n：7
拆分为相等子集合的方案数：4 
*/